package mess;

import java.util.ArrayList;
import java.util.List;

public class LeeCode_17 {
    public static void main(String[] args) {
        System.out.println(letterCombinations("23456789435"));
    }

    private static List<String> letterCombinations(String digits) {
        String[] letters = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        List<String> result = new ArrayList<>();
        int len = digits.length();
        if (len == 0) {
            return result;
        }
        int first = digits.charAt(0) - 48;
        String firstStr = letters[first];
        for (int i = 0; i < firstStr.length(); i++)
            result.add(firstStr.charAt(i) + "");
        for (int i = 1; i < len; i++) {
            List<String> tempList = new ArrayList<>();
            tempList.addAll(result);
            int num = digits.charAt(i) - 48;
            String numStr = letters[num];
            int len2 = numStr.length();
            int len3 = tempList.size();
            for (int j = 0; j < len2; j++) {
                char c = numStr.charAt(j);
                for (int k = 0; k < len3; k++) {
                    int index = j * len3 + k;
                    result.set(index, result.get(index) + c);
                }
                if (j < len2 - 1)
                    result.addAll(tempList);
            }
        }
        return result;
    }
}
